package jjn.round1;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author Jjn
 * @since 2022/9/21 00:00
 */
public class LeetCode17_LetterCombinationOfPhoneNumber {
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return result;
        }
        Map<Character, String> map = new HashMap<>();
        map.put('0', " ");
        map.put('1', "");
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");
        backtrack(result, digits, new char[digits.length()], 0, map);
        return result;
    }

    /**
     * Backtrack.
     *
     * @param result     result
     * @param digits     digits
     * @param characters chosen characters
     * @param stage      current decision stage
     * @param map        character -> available words
     */
    private void backtrack(List<String> result, String digits, char[] characters, int stage, Map<Character, String> map) {
        // Already used all the characters.
        if (stage == digits.length()) {
            // Add to result set.
            result.add(new String(characters));
            return;
        }
        // Find mapped characters.
        String s = map.get(digits.charAt(stage));
        for (int i = 0; i < s.length(); i++) {
            characters[stage] = s.charAt(i);
            backtrack(result, digits, characters, stage + 1, map);
        }
    }
}
